import java.util.PriorityQueue;


class MedianFinder {
    PriorityQueue<Integer> MIN;
    PriorityQueue<Integer> MAX;
    int count = 0;

    /**
     * initialize your data structure here.
     */
    public MedianFinder() {
        MIN = new PriorityQueue<>((a, b) -> b - a);
        MAX = new PriorityQueue<>((a, b) -> a - b);
    }

    public void addNum(int num) {
        if (count % 2 == 0) {
            if (MIN.size() == 0) {
                MIN.offer(num);
            } else if (MIN.peek() >= num) {
                MIN.offer(num);
            } else {
                MAX.offer(num);
                MIN.offer(MAX.poll());
            }
        } else {
            if (num > MIN.peek()) {
                MAX.offer(num);
            } else {
                MIN.offer(num);
                MAX.offer(MIN.poll());
            }
        }
        count++;
    }

    public double findMedian() {
        if (count % 2 == 0) {
            return ((double) MIN.peek() + MAX.peek()) / 2;
        } else {
            return (double)MIN.peek();
        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
